/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package algo.utilitaire;

import algo.graphe.Graphe;
import java.util.LinkedList;

/**
 * Outils utiles pour le parcours de graphe
 * @author uapv9900036
 */
public class UtilitaireParcours {

    /**
     * Fait un parcours en largeur d'une graphe
     * @return Le tableau des sommet visité
     */
    public static boolean[] parcoursLargeur(Graphe g, boolean[] visited, int begin) {
        LinkedList<Integer> file = new LinkedList<Integer>();
        int[][] matrice = g.getMatriceAdj();
        if (visited == null) {
            visited = new boolean[matrice.length];
            for (int i = 0; i < matrice.length; i++) {
                visited[i] = false;
            } // for
        }
        boolean[] voisins;
        //  Insertion du premier sommet
        file.addLast(begin);

        while (!file.isEmpty()) {
            int s = file.removeFirst();

            if (visited[s] != true) {
                visited[s] = true;

                voisins = UtilitaireParcours.voisins(s, g);

                for (int i = 0; i < voisins.length; i++) {
                    //  si c'est vraiment un voisin
                    if (voisins[i] == true) {
                        //  verification si le voisin a déja été visité
                        if (visited[i] != true) {
                            file.addLast(i);
                        } // if
                    } // if
                } // for

            } // if
        } // while

        return visited;
    }

    /**
     * Fait un parcours en profondeur du graphe
     * @return
     */
    public static boolean[] parcoursProfondeur(Graphe g, boolean[] visited, int begin) {
        LinkedList<Integer> pile = new LinkedList<Integer>();

        int[][] matrice = g.getMatriceAdj();

        if (visited == null) {
            visited = new boolean[matrice.length];
        }

        boolean[] voisins;
        for (int i = 0; i < matrice.length; i++) {
            visited[i] = false;
        } // for

        //  Insertion du premier sommet
        pile.addFirst(begin);

        while (!pile.isEmpty()) {
            int s = pile.removeFirst();

            if (visited[s] != true) {
                visited[s] = true;

                voisins = UtilitaireParcours.voisins(s, g);

                for (int i = 0; i < voisins.length; i++) {
                    //  si c'est vraiment un voisin
                    if (voisins[i] == true) {
                        //  verification si le voisin a déja été visité
                        if (visited[i] != true) {
                            pile.addFirst(i);
                        } // if
                    } // if
                } // for

            } // if
        } // while

        return visited;
    }

    /**
     * Retourne les voisins/Successeur d'un sommet d'un graphe
     * @param node
     * @return
     */
    public static boolean[] voisins(int node, Graphe g) {
        return g.successeurs(node);
    }
}
